package Leetcode.数组字符串;

/**
 * @Author: kirito
 * @Date: 2024/3/19 13:59
 * @Description:
 * 给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
 *
 * 一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
 *
 * 请你返回 好 子数组的最大可能 分数 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,4,3,7,4,5], k = 3
 * 输出：15
 * 解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。
 * 示例 2：
 *
 * 输入：nums = [5,5,4,5,4,1,1,1], k = 0
 * 输出：20
 * 解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 2 * 104
 * 0 <= k < nums.length
 *
 * 在给定的数组 nums 中找到以索引 k 为中心的最大得分。这里的得分定义为，以 nums[k] 为高度，
 * 向左和向右扩展，直到遇到比 nums[k] 小的元素，然后计算这个区域的面积（即宽度乘以高度）。
 */

public class maximumScore {
    public int maximumScore(int[] nums, int k) {
        int n = nums.length;  // 获取数组的长度
        int left = k - 1, right = k + 1;  // 初始化左右指针，分别指向k的左侧和右侧
        int ans = 0;  // 初始化最大得分

        for (int i = nums[k];;
//             --i
        ) {  // 从nums[k]的高度开始递减循环
            while (left >= 0 && nums[left] >= i) {  // 向左移动left指针直到遇到小于当前高度的元素
                --left;
            }
            while (right < n && nums[right] >= i) {  // 向右移动right指针直到遇到小于当前高度的元素
                ++right;
            }
            ans = Math.max(ans, (right - left - 1) * i);  // 计算当前高度的得分，并更新最大得分
            if (left == -1 && right == n) {  // 如果左右指针都到达边界，说明无法找到更大的得分，退出循环
                break;
            }
            //上面的循环是左边界和右边界的高度是一定大于等于i的，所以i--每次步长就太小了
            //可以直接把i定位到左右两边界的最大值
            i = Math.max((left == -1 ? -1 : nums[left]), (right == n ? -1 : nums[right]));
            if (i == -1) {
                break;
            }
        }
        return ans;  // 返回最大得分
    }

}
